home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / prog / wf120.zip / MATCH.C next >
C/C++ Source or Header  |  1992-01-06  |  19KB  |  579 lines
  1. /*
  2.  EPSHeader
  3.  
  4.    File: match.c
  5.    Author: J. Kercheval
  6.    Created: Sat, 01/05/1991  22:21:49
  7. */
  8.  
  9. /*
  10.  EPSRevision History
  11.  
  12.    J. Kercheval  Wed, 02/20/1991  22:29:01  Released to Public Domain
  13.    J. Kercheval  Fri, 02/22/1991  15:29:01  fix '\' bugs (two :( of them)
  14.    J. Kercheval  Sun, 03/10/1991  19:31:29  add error return to matche()
  15.    J. Kercheval  Sun, 03/10/1991  20:11:11  add is_valid_pattern code
  16.    J. Kercheval  Sun, 03/10/1991  20:37:11  beef up main()
  17.    J. Kercheval  Tue, 03/12/1991  22:25:10  Released as V1.1 to Public Domain
  18.    J. Kercheval  Thu, 03/14/1991  22:22:25  remove '\' for DOS file parsing
  19.    J. Kercheval  Mon, 05/13/1991  21:49:05  ifdef full match code
  20.    J. Kercheval  Mon, 01/06/1992  21:31:44  add match character defines
  21. */
  22.  
  23. /*
  24.  * Wildcard Pattern Matching
  25.  */
  26.  
  27.  
  28. #include "match.h"
  29.  
  30. /* character defines */
  31. #define MATCH_CHAR_SINGLE               '?'
  32. #define MATCH_CHAR_KLEENE_CLOSURE       '*'
  33. #define MATCH_CHAR_RANGE_OPEN           '['
  34. #define MATCH_CHAR_RANGE                '-'
  35. #define MATCH_CHAR_RANGE_CLOSE          ']'
  36. #define MATCH_CHAR_LITERAL              '\\'
  37. #define MATCH_CHAR_NULL                 '\0'
  38. #define MATCH_CHAR_CARAT_NEGATE         '^'
  39. #define MATCH_CHAR_EXCLAMATION_NEGATE   '!'
  40.  
  41. /* forward function prototypes */
  42. int matche_after_star(register char *pattern, register char *text);
  43. int fast_match_after_star(register char *pattern, register char *text);
  44.  
  45.  
  46. /*----------------------------------------------------------------------------
  47.  *
  48.  * Return TRUE if PATTERN has any special wildcard characters
  49.  *
  50.  ---------------------------------------------------------------------------*/
  51.  
  52. BOOLEAN is_pattern(char *p)
  53. {
  54.     while (*p) {
  55.         switch (*p++) {
  56.                 case MATCH_CHAR_SINGLE:
  57.                 case MATCH_CHAR_KLEENE_CLOSURE:
  58.                 case MATCH_CHAR_RANGE_OPEN:
  59.  
  60. #ifndef FILE_MATCH
  61.                 case MATCH_CHAR_LITERAL:
  62. #endif
  63.  
  64.                 return TRUE;
  65.         }
  66.     }
  67.     return FALSE;
  68. }
  69.  
  70.  
  71. /*----------------------------------------------------------------------------
  72.  *
  73.  * Return TRUE if PATTERN has is a well formed regular expression according
  74.  * to the above syntax
  75.  *
  76.  * error_type is a return code based on the type of pattern error.  Zero is
  77.  * returned in error_type if the pattern is a valid one.  error_type return
  78.  * values are as follows:
  79.  *
  80.  *   PATTERN_VALID - pattern is well formed
  81.  
  82. #ifndef FILE_MATCH
  83.  *   PATTERN_ESC   - pattern has invalid escape ('\' at end of pattern)
  84. #endif
  85.  
  86.  *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  87.  *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  88.  *   PATTERN_EMPTY - [..] construct is empty (ie [])
  89.  *
  90.  ---------------------------------------------------------------------------*/
  91.  
  92. BOOLEAN is_valid_pattern(char *p, int *error_type)
  93. {
  94.  
  95.     /* init error_type */
  96.     *error_type = PATTERN_VALID;
  97.  
  98.     /* loop through pattern to EOS */
  99.     while (*p) {
  100.  
  101.         /* determine pattern type */
  102.         switch (*p) {
  103.  
  104. #ifndef FILE_MATCH
  105.                 /* check literal escape, it cannot be at end of pattern */
  106.             case MATCH_CHAR_LITERAL:
  107.                 if (!*++p) {
  108.                     *error_type = PATTERN_ESC;
  109.                     return FALSE;
  110.                 }
  111.                 p++;
  112.                 break;
  113. #endif
  114.  
  115.                 /* the [..] construct must be well formed */
  116.             case MATCH_CHAR_RANGE_OPEN:
  117.                 p++;
  118.  
  119.                 /* if the next character is ']' then bad pattern */
  120.                 if (*p == MATCH_CHAR_RANGE_CLOSE) {
  121.                     *error_type = PATTERN_EMPTY;
  122.                     return FALSE;
  123.                 }
  124.  
  125.                 /* if end of pattern here then bad pattern */
  126.                 if (!*p) {
  127.                     *error_type = PATTERN_CLOSE;
  128.                     return FALSE;
  129.                 }
  130.  
  131.                 /* loop to end of [..] construct */
  132.                 while (*p != MATCH_CHAR_RANGE_CLOSE) {
  133.  
  134.                     /* check for literal escape */
  135.                     if (*p == MATCH_CHAR_LITERAL) {
  136.                         p++;
  137.  
  138.                         /* if end of pattern here then bad pattern */
  139.                         if (!*p++) {
  140.                             *error_type = PATTERN_ESC;
  141.                             return FALSE;
  142.                         }
  143.                     }
  144.                     else
  145.                         p++;
  146.  
  147.                     /* if end of pattern here then bad pattern */
  148.                     if (!*p) {
  149.                         *error_type = PATTERN_CLOSE;
  150.                         return FALSE;
  151.                     }
  152.  
  153.                     /* if this a range */
  154.                     if (*p == MATCH_CHAR_RANGE) {
  155.  
  156.                         /* we must have an end of range */
  157.                         if (!*++p || *p == MATCH_CHAR_RANGE_CLOSE) {
  158.                             *error_type = PATTERN_RANGE;
  159.                             return FALSE;
  160.                         }
  161.                         else {
  162.  
  163.                             /* check for literal escape */
  164.                             if (*p == MATCH_CHAR_LITERAL)
  165.                                 p++;
  166.  
  167.                             /* if end of pattern here then bad pattern */
  168.                             if (!*p++) {
  169.                                 *error_type = PATTERN_ESC;
  170.                                 return FALSE;
  171.                             }
  172.                         }
  173.                     }
  174.                 }
  175.                 break;
  176.  
  177.                 /* all other characters are valid pattern elements */
  178.             case MATCH_CHAR_KLEENE_CLOSURE:
  179.             case MATCH_CHAR_SINGLE:
  180.             default:            /* "normal" character */
  181.                 p++;
  182.                 break;
  183.         }
  184.     }
  185.  
  186.     return TRUE;
  187. }
  188.  
  189.  
  190. /*----------------------------------------------------------------------------
  191.  *
  192.  * Match the pattern PATTERN against the string TEXT;
  193.  *
  194.  * returns MATCH_VALID if pattern matches, or an errorcode as follows
  195.  * otherwise:
  196.  *
  197.  *           MATCH_PATTERN  - bad pattern
  198.  
  199. #ifndef FILE_MATCH
  200.  *           MATCH_LITERAL  - match failure on literal mismatch
  201. #endif
  202.  
  203.  *           MATCH_RANGE    - match failure on [..] construct
  204.  *           MATCH_ABORT    - premature end of text string
  205.  *           MATCH_END      - premature end of pattern string
  206.  *           MATCH_VALID    - valid match
  207.  *
  208.  *
  209.  * A match means the entire string TEXT is used up in matching.
  210.  *
  211.  * In the pattern string:
  212.  *      `*' matches any sequence of characters (zero or more)
  213.  *      `?' matches any character
  214.  *      [SET] matches any character in the specified set,
  215.  *      [!SET] or [^SET] matches any character not in the specified set.
  216.  *      \ is allowed within a set to escape a character like ']' or '-'
  217.  *
  218.  * A set is composed of characters or ranges; a range looks like character
  219.  * hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the minimal set of
  220.  * characters allowed in the [..] pattern construct.  Other characters are
  221.  * allowed (ie. 8 bit characters) if your system will support them.
  222.  *
  223.  * To suppress the special syntactic significance of any of `[]*?!^-\', and
  224.  * match the character exactly, precede it with a `\'.
  225.  *
  226.  ---------------------------------------------------------------------------*/
  227.  
  228. int matche(register char *p, register char *t)
  229. {
  230.     register char range_start, range_end;       /* start and end in range */
  231.  
  232.     BOOLEAN invert;             /* is this [..] or [!..] */
  233.     BOOLEAN member_match;       /* have I matched the [..] construct? */
  234.     BOOLEAN loop;               /* should I terminate? */
  235.  
  236.     for (; *p; p++, t++) {
  237.  
  238.         /* if this is the end of the text then this is the end of the match */
  239.         if (!*t) {
  240.             return (*p == MATCH_CHAR_KLEENE_CLOSURE &&
  241.                     *++p == MATCH_CHAR_NULL) ?
  242.                 MATCH_VALID : MATCH_ABORT;
  243.         }
  244.  
  245.         /* determine and react to pattern type */
  246.         switch (*p) {
  247.  
  248.                 /* single any character match */
  249.             case MATCH_CHAR_SINGLE:
  250.                 break;
  251.  
  252.                 /* multiple any character match */
  253.             case MATCH_CHAR_KLEENE_CLOSURE:
  254.                 return matche_after_star(p, t);
  255.  
  256.                 /* [..] construct, single member/exclusion character match */
  257.             case MATCH_CHAR_RANGE_OPEN:{
  258.  
  259.                     /* move to beginning of range */
  260.                     p++;
  261.  
  262.                     /* check if this is a member match or exclusion match */
  263.                     invert = FALSE;
  264.                     if (*p == MATCH_CHAR_EXCLAMATION_NEGATE ||
  265.                         *p == MATCH_CHAR_CARAT_NEGATE) {
  266.                         invert = TRUE;
  267.                         p++;
  268.                     }
  269.  
  270.                     /* if closing bracket here or at range start then we have
  271.                      * a malformed pattern */
  272.                     if (*p == MATCH_CHAR_RANGE_CLOSE) {
  273.                         return MATCH_PATTERN;
  274.                     }
  275.  
  276.                     member_match = FALSE;
  277.                     loop = TRUE;
  278.  
  279.                     while (loop) {
  280.  
  281.                         /* if end of construct then loop is done */
  282.                         if (*p == MATCH_CHAR_RANGE_CLOSE) {
  283.                             loop = FALSE;
  284.                             continue;
  285.                         }
  286.  
  287.                         /* matching a '!', '^', '-', '\' or a ']' */
  288.                         if (*p == MATCH_CHAR_LITERAL) {
  289.                             range_start = range_end = *++p;
  290.                         }
  291.                         else {
  292.                             range_start = range_end = *p;
  293.                         }
  294.  
  295.                         /* if end of pattern then bad pattern (Missing ']') */
  296.                         if (!*p)
  297.                             return MATCH_PATTERN;
  298.  
  299.                         /* check for range bar */
  300.                         if (*++p == MATCH_CHAR_RANGE) {
  301.  
  302.                             /* get the range end */
  303.                             range_end = *++p;
  304.  
  305.                             /* if end of pattern or construct then bad
  306.                              * pattern */
  307.                             if (range_end == MATCH_CHAR_NULL ||
  308.                                 range_end == MATCH_CHAR_RANGE_CLOSE)
  309.                                 return MATCH_PATTERN;
  310.  
  311.                             /* special character range end */
  312.                             if (range_end == MATCH_CHAR_LITERAL) {
  313.                                 range_end = *++p;
  314.  
  315.                                 /* if end of text then we have a bad pattern */
  316.                                 if (!range_end)
  317.                                     return MATCH_PATTERN;
  318.                             }
  319.  
  320.                             /* move just beyond this range */
  321.                             p++;
  322.                         }
  323.  
  324.                         /* if the text character is in range then match
  325.                          * found. make sure the range letters have the proper
  326.                          * relationship to one another before comparison */
  327.                         if (range_start < range_end) {
  328.                             if (*t >= range_start && *t <= range_end) {
  329.                                 member_match = TRUE;
  330.                                 loop = FALSE;
  331.                             }
  332.                         }
  333.                         else {
  334.                             if (*t >= range_end && *t <= range_start) {
  335.                                 member_match = TRUE;
  336.                                 loop = FALSE;
  337.                             }
  338.                         }
  339.                     }
  340.  
  341.                     /* if there was a match in an exclusion set then no match */
  342.                     /* if there was no match in a member set then no match */
  343.                     if ((invert && member_match) ||
  344.                         !(invert || member_match))
  345.                         return MATCH_RANGE;
  346.  
  347.                     /* if this is not an exclusion then skip the rest of the
  348.                      * [...] construct that already matched. */
  349.                     if (member_match) {
  350.                         while (*p != MATCH_CHAR_RANGE_CLOSE) {
  351.  
  352.                             /* bad pattern (Missing MATCH_CHAR_RANGE_CLOSE) */
  353.                             if (!*p)
  354.                                 return MATCH_PATTERN;
  355.  
  356.                             /* skip exact match */
  357.                             if (*p == MATCH_CHAR_LITERAL) {
  358.                                 p++;
  359.  
  360.                                 /* if end of text then we have a bad pattern */
  361.                                 if (!*p)
  362.                                     return MATCH_PATTERN;
  363.                             }
  364.  
  365.                             /* move to next pattern char */
  366.                             p++;
  367.                         }
  368.                     }
  369.  
  370.                     break;
  371.                 }
  372.  
  373. #ifndef FILE_MATCH
  374.                 /* next character is quoted and must match exactly */
  375.             case MATCH_CHAR_LITERAL:
  376.  
  377.                 /* move pattern pointer to quoted char and fall through */
  378.                 p++;
  379.  
  380.                 /* if end of text then we have a bad pattern */
  381.                 if (!*p)
  382.                     return MATCH_PATTERN;
  383. #endif
  384.  
  385.                 /* must match this character exactly */
  386.             default:
  387.                 if (*p != *t)
  388.                     return MATCH_LITERAL;
  389.         }
  390.     }
  391.  
  392.     /* if end of text not reached then the pattern fails */
  393.     if (*t)
  394.         return MATCH_END;
  395.     else
  396.         return MATCH_VALID;
  397. }
  398.  
  399.  
  400. /*----------------------------------------------------------------------------
  401.  *
  402.  * recursively call matche() with final segment of PATTERN and of TEXT.
  403.  *
  404.  ---------------------------------------------------------------------------*/
  405.  
  406. int matche_after_star(register char *p, register char *t)
  407. {
  408.     register int match = 0;
  409.     register nextp;
  410.  
  411.     /* pass over existing ? and * in pattern */
  412.     while (*p == MATCH_CHAR_SINGLE ||
  413.            *p == MATCH_CHAR_KLEENE_CLOSURE) {
  414.  
  415.         /* take one char for each ? and + */
  416.         if (*p == MATCH_CHAR_SINGLE) {
  417.  
  418.             /* if end of text then no match */
  419.             if (!*t++) {
  420.                 return MATCH_ABORT;
  421.             }
  422.         }
  423.  
  424.         /* move to next char in pattern */
  425.         p++;
  426.     }
  427.  
  428.     /* if end of pattern we have matched regardless of text left */
  429.     if (!*p) {
  430.         return MATCH_VALID;
  431.     }
  432.  
  433.     /* get the next character to match which must be a literal or '[' */
  434.     nextp = *p;
  435.  
  436. #ifndef FILE_MATCH
  437.     if (nextp == MATCH_CHAR_LITERAL) {
  438.         nextp = p[1];
  439.  
  440.         /* if end of text then we have a bad pattern */
  441.         if (!nextp)
  442.             return MATCH_PATTERN;
  443.     }
  444. #endif
  445.  
  446.     /* Continue until we run out of text or definite result seen */
  447.     do {
  448.  
  449.         /* a precondition for matching is that the next character in the
  450.          * pattern match the next character in the text or that the next
  451.          * pattern char is the beginning of a range.  Increment text pointer
  452.          * as we go here */
  453.         if (nextp == *t || nextp == MATCH_CHAR_RANGE_OPEN) {
  454.             match = matche(p, t);
  455.         }
  456.  
  457.         /* if the end of text is reached then no match */
  458.         if (!*t++)
  459.             match = MATCH_ABORT;
  460.  
  461.     } while (match != MATCH_VALID &&
  462.              match != MATCH_ABORT &&
  463.              match != MATCH_PATTERN);
  464.  
  465.     /* return result */
  466.     return match;
  467. }
  468.  
  469.  
  470. /*----------------------------------------------------------------------------
  471.  *
  472.  * match() is a shell to matche() to return only BOOLEAN values.
  473.  *
  474.  ---------------------------------------------------------------------------*/
  475.  
  476. BOOLEAN match(char *p, char *t)
  477. {
  478.     int error_type;
  479.  
  480.     error_type = matche(p, t);
  481.     return (error_type == MATCH_VALID) ? TRUE : FALSE;
  482. }
  483.  
  484.  
  485. #ifdef TEST
  486.  
  487. /*
  488.     * This test main expects as first arg the pattern and as second arg
  489.     * the match string.  Output is yaeh or nay on match.  If nay on
  490.     * match then the error code is parsed and written.
  491. */
  492.  
  493. #include <stdio.h>
  494.  
  495. int main(int argc, char *argv[])
  496. {
  497.     int error;
  498.     int is_valid_error;
  499.  
  500.     if (argc != 3) {
  501.         printf("Usage:  MATCH Pattern Text\n");
  502.     }
  503.     else {
  504.         printf("Pattern: %s\n", argv[1]);
  505.         printf("Text   : %s\n", argv[2]);
  506.  
  507.         if (!is_pattern(argv[1])) {
  508.             printf("    First Argument Is Not A Pattern\n");
  509.         }
  510.         else {
  511.  
  512. #ifdef FILE_MATCH
  513.             match(argv[1], argv[2]) ? printf("TRUE") : printf("FALSE");
  514. #endif
  515.  
  516.             error = matche(argv[1], argv[2]);
  517.             is_valid_pattern(argv[1], &is_valid_error);
  518.  
  519.             switch (error) {
  520.                 case MATCH_VALID:
  521.                     printf("    Match Successful");
  522.                     if (is_valid_error != PATTERN_VALID)
  523.                         printf(" -- is_valid_pattern() is complaining\n");
  524.                     else
  525.                         printf("\n");
  526.                     break;
  527.  
  528. #ifndef FILE_MATCH
  529.                 case MATCH_LITERAL:
  530.                     printf("    Match Failed on Literal\n");
  531.                     break;
  532. #endif
  533.  
  534.                 case MATCH_RANGE:
  535.                     printf("    Match Failed on [..]\n");
  536.                     break;
  537.                 case MATCH_ABORT:
  538.                     printf("    Match Failed on Early Text Termination\n");
  539.                     break;
  540.                 case MATCH_END:
  541.                     printf("    Match Failed on Early Pattern Termination\n");
  542.                     break;
  543.                 case MATCH_PATTERN:
  544.                     switch (is_valid_error) {
  545.                         case PATTERN_VALID:
  546.                             printf("    Internal Disagreement On Pattern\n");
  547.                             break;
  548.  
  549. #ifndef FILE_MATCH
  550.                         case PATTERN_ESC:
  551.                             printf("    Literal Escape at End of Pattern\n");
  552.                             break;
  553. #endif
  554.  
  555.                         case PATTERN_RANGE:
  556.                             printf("    No End of Range in [..] Construct\n");
  557.                             break;
  558.                         case PATTERN_CLOSE:
  559.                             printf("    [..] Construct is Open\n");
  560.                             break;
  561.                         case PATTERN_EMPTY:
  562.                             printf("    [..] Construct is Empty\n");
  563.                             break;
  564.                         default:
  565.                             printf("    Internal Error in is_valid_pattern()\n");
  566.                     }
  567.                     break;
  568.                 default:
  569.                     printf("    Internal Error in matche()\n");
  570.                     break;
  571.             }
  572.         }
  573.  
  574.     }
  575.     return (0);
  576. }
  577.  
  578. #endif
  579.